package org.example.top40;

public class main33 {
    //环形链表Ⅱ
    //输入：head = [3,2,0,-4], pos = 1
    //输出：返回索引为 1 的链表节点
    //思路：快慢指针，找到是环的，此刻开始创建新节点，一个指向head一个指向fast，开始移动直到相等为止return
    //原理：2*(x+y)=x+y+n*(z+y)
    //x=(n-1)(y+z)+z  即index1走的路程=index2从相遇节点开始绕圈走的路程
    public static void main(String[] args) {
        ListNode head = builder();
        ListNode node = cycle(head);
        System.out.println(node.val);
    }
    private static ListNode cycle(ListNode head){
        ListNode slow=head;
        ListNode fast=head;
        while (fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                ListNode index1=head;
                ListNode index2=fast;
                while (index1!=index2){
                    index1=index1.next;
                    index2=index2.next;
                }
                return index1;
            }
        }
        return null;
    }
    private static ListNode builder(){
        ListNode head = new ListNode(3);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(0);
        ListNode node3 = new ListNode(-4);
        head.next=node1;
        node1.next=node2;
        node2.next=node3;
        node3.next=node1;
        return head;
    }
}
